import javafx.util.Pair;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public static void main(String[] args) {

    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;this.left = left;
            this.right = right;
        }
    }

    public int widthOfBinaryTree(TreeNode root) {
        /**
         * 二叉树的最大宽度
         * 解题思路：
         *  对每一个节点都增加线性存储时的编号，后续使用编号计算宽度
         *  编号从1开始，左孩子为 2x，右孩子为2x+1
         * 思路总结：
         *  依旧是使用BFS进行遍历，但是对每个节点进行编号处理，这样即可通过编号得知本层长度
         *  此处有一个知识点：当二叉树层数够深时，编号可能会溢出，但由于是做减法且溢出值相同，故相对差值不变，结果正确*/
        // 1 预处理
        int maxLength = 1;
        Deque<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 1));

        // 2 BFS层序遍历
        while(!queue.isEmpty()) {
            // -1 记录当前层节点个数
            int n = queue.size();

            // -2 出队
            for(int i = 0; i < n; i++) {
                Pair<TreeNode, Integer> cur = queue.poll();
                TreeNode curNode = cur.getKey();
                int curValue = cur.getValue();
                // -仅当节点不为空时再入队
                if(curNode.left != null) {
                    queue.offer(new Pair<>(curNode.left, curValue*2));
                }
                if(curNode.right != null) {
                    queue.offer(new Pair<>(curNode.right, curValue*2+1));
                }
            }

            // -3 计算本层宽度（含空）
            if(!queue.isEmpty()) {
                int curLength = queue.peekLast().getValue() - queue.peekFirst().getValue() + 1;
                if(curLength > maxLength) {
                    maxLength = curLength;
                }
            }
        }

        // 3 返回值
        return maxLength;
    }
}
